package fun.ticsmyc.question;

import fun.ticsmyc.tools.TreeNode;
import org.junit.Test;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-02-21 12:26
 */
public class 完全二叉树节点个数 {

    public int numberOfTreeNodes(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftHeight =1;
        int rightHeight = 1;
        TreeNode cur = root;
        while(cur.left!=null){
            leftHeight++;
            cur=cur.left;
        }
        cur=root;
        while(cur.right!= null){
            rightHeight++;
            cur=cur.right;
        }

        if(leftHeight == rightHeight){
            //左右高度一致，则这颗树是完全二叉树，直接返回节点数
            return (int)Math.pow(2,leftHeight)-1;
        }else{
            return 1+numberOfTreeNodes(root.left)+numberOfTreeNodes(root.right);
        }
    }

    @Test
    public void test(){
        TreeNode head = new TreeNode(5);
        head.left = new TreeNode(3);
        head.right = new TreeNode(8);
        head.left.left = new TreeNode(2);
        head.left.right = new TreeNode(4);
        System.out.println(numberOfTreeNodes(head));
    }


}
